Batch 3 - Class 232 - Information and Encryption II

• Research - Enigma encryption device and The Bomb, which broke the enigma codes
• Build a shift cipher device at home

• Review of previous class (Ciphers and ways of breaking them)
• Shift/Caeser Cipher
• Substitution Cipher
• Polyalphabetic Ciphers

• Polyalphabetic Cipher 
• How would you use this for maximum secrecy? One time pad - make the code as large as the message itself (but basis a key that generates the one-time pad)
• Polyalphabetic ciphers were used in World War II, and finally broken by Enigma  https://en.wikipedia.org/wiki/Enigma_machine

• A one-time pad makes the frequency of letters random. However, what is truly random? 
• Let kids specify what they mean by random? Show them a random looking stream of 0s and 1s and ask them if its random.
• Randomness is not just a function of number of 0s and 1s. Any other pattern taken from the string should also have equal probability
• Lets test how random you are  https://www.khanacademy.org/computing/computer-science/cryptography/crypt/pi/how-uniform-are-you
• Kids will notice that while their 0s and 1s might be similar in numbers, the other patterns break down. 
• One example of pseudo-random number generator is the middle square method. Take a random seed (measure from electrical noise, or current time in millisecond. Now square it, and take the middle three digits. Repeat.
• Pseudo random sequences eventually repeat, when we reach a sequence we have previously encountered. The repetition period depends on key length, and strength of pseudo-random algorithm.
• Difference between code (like Morse code) and Cipher
• Compression and signaling, versus secrecy

• Key Sharing - how do we share keys - the problem of secrecy of messages is now translated to secrecy of keys
• Pre-shared lists of keys
• How would we share keys between people who have never met?
• Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the world of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?
• Answer: Jan sends Maria a box with the ring in it and one of his padlocks on it. Upon receipt Maria affixes her own padlock to box and mails it back with both padlocks on it. When Jan gets it he removes his padlock and sends the box back to Maria; voila! This solution is not just play; the idea is fundamental in Diffie-Hellman key exchange, a historic breakthrough in cryptography.
• One way functions - easy in one direction, hard in the other
• Color exercise from khan academy https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-1 - one way function here is mixing colors
• Diffie Hellman: p^x mod q as a one way function, if p and q are primes, and this function distributes uniformly - p and q are agreed. private keys are x's and result of mods are sent out publicly. substituting p by the shared mod, gives the shared secret.

• Public-Private Key Encryption
• What if each of us has to communicate with millions of other people (like a bank)? Having many pairs of keys is hard. Analogy of a "clip lock". Color example on khan academy (alter the machine as something which can tell you a pair of complementary colors, but there is no way to determine a complementary color of a given color)
• Other applications - authentication using public keys; secrecy and authentication?

• Read "The Adventures of the Dancing Men", a Sherlock Homes story. Or solve it here www.aamt.edu.au/content/download/18716/.../nmd12_dancing_men.pdf